import java.util.HashSet;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2023-02-23
 * Time: 10:52
 */
public class Day17 {
    //748.最短补全词 - 标记
    public String shortestCompletingWord(String licensePlate, String[] words) {
        int[] answer = new int[26];

        char[] lp = licensePlate.toLowerCase().toCharArray();
        for (int i = 0; i < lp.length; i++) {
            if (lp[i] >= 'a' && lp[i] <= 'z'){
                answer[lp[i] - 'a']++;
            }
        }

        int index = -1;
        for (int i = 0; i < words.length; i++) {
            int[] ret = new int[26];
            char[] ws = words[i].toCharArray();

            for (int j = 0; j < ws.length; j++) {
                ret[ws[j] - 'a']++;
            }

            boolean flag = true;
            for (int j = 0; j < 26; j++) {
                if (ret[j] < answer[j]){
                    flag = false;
                    break;
                }
            }

            if (flag && (index < 0 || words[i].length()  < words[index].length())){
                index = i;
            }
        }

        return words[index];
    }

    //766.托普利茨矩阵 - 标记
    public boolean isToeplitzMatrix(int[][] matrix) {
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][j] != matrix[i - 1][j - 1]){
                    return false;
                }
            }
        }
        return true;
    }

    //804.唯一摩尔斯密码词
    public static String[] Morse = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
    public int uniqueMorseRepresentations(String[] words) {
        if (words == null){
            return 0;
        }
        Set<String> set = new HashSet<>();
        for (int i = 0; i < words.length; i++) {
            StringBuilder sb = new StringBuilder();
            char[] ws = words[i].toCharArray();
            for (int j = 0; j < ws.length; j++) {
                sb.append(Morse[ws[j] - 'a']);
            }
            set.add(sb.toString());
        }
        return set.size();
    }

    //806.写字符需要的行数
    public int[] numberOfLines(int[] widths, String s) {
        int[] answer = new int[2];
        answer[0] = 1;

        char[] ss = s.toCharArray();
        for (int i = 0; i < ss.length; i++) {
            answer[1] += widths[ss[i] - 'a'];
            if (answer[1] > 100){
                answer[1] = widths[ss[i] - 'a'];
                answer[0]++;
            }
        }
        return answer;
    }

    //812.最大三角形面积
    public double largestTriangleArea(int[][] points) {
        int n = points.length;
        double ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    ret = Math.max(ret, Max(points[i][0], points[i][1], points[j][0], points[j][1], points[k][0], points[k][1]));
                }
            }
        }
        return ret;
    }
    public static double Max(int x1, int y1, int x2, int y2, int x3, int y3){
        return 0.5*Math.abs(x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2);
    }

    //821.字符的最短距离
    public int[] shortestToChar(String s, char c){
        char[] ss = s.toCharArray();
        int[] answer = new int[ss.length];

        int n = ss.length;
        for (int i = 0, index = -n; i < n; i++) {
            if (ss[i] == c){
                index = i;
            }
            answer[i] = i - index;
        }

        for (int i = n - 1, index = 2*n; i >= 0; i--) {
            if (ss[i] == c){
                index = i;
            }
            answer[i] = Math.min(answer[i], index - i);
        }

        return answer;
    }
}
